package leetcode.editor.cn.dsa04_queue;
//返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。
//
// 如果没有和至少为 K 的非空子数组，返回 -1 。 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 输入：A = [1], K = 1
//输出：1
// 
//
// 示例 2： 
//
// 输入：A = [1,2], K = 4
//输出：-1
// 
//
// 示例 3： 
//
// 输入：A = [2,-1,2], K = 3
//输出：3
// 
//
// 
//
// 提示： 
//
// 
// 1 <= A.length <= 50000 
// -10 ^ 5 <= A[i] <= 10 ^ 5 
// 1 <= K <= 10 ^ 9 
// 
// Related Topics 队列 二分查找 
// 👍 229 👎 0

class ShortestSubarrayWithSumAtLeastK862{
    public static void main(String[] args) {
        Solution solution = new ShortestSubarrayWithSumAtLeastK862().new Solution();
        int[] arr = {0,6,-1,2,3,5,9,8,-3,-4,10};
        System.out.println(solution.shortestSubarray(arr, 15)); //2
        System.out.println(solution.shortestSubarray(arr, 23)); //4
        int[] arr2 = {1};
        System.out.println(solution.shortestSubarray(arr2, 1)); //1
        int[] arr3 = {1,2};
        System.out.println(solution.shortestSubarray(arr3, 4)); //-1
        int[] arr4 = {2,-1,2};
        System.out.println(solution.shortestSubarray(arr4, 3)); //3
        int[] arr5 = {84,-37,32,40,95};
        System.out.println(solution.shortestSubarray(arr5, 167)); //3
        int[] arr6 = {27,20,79,87,-36,78,76,72,50,-26};
        System.out.println(solution.shortestSubarray(arr6, 453)); //9
        int[] arr7 = {-28,81,-20,28,-29};
        System.out.println(solution.shortestSubarray(arr7, 89)); //3
        int[] arr8 = {-34,37,51,3,-12,-50,51,100,-47,99,34,14,-13,89,31,-14,-44,23,-38,6};
        System.out.println(solution.shortestSubarray(arr8, 151)); //2
        int[] arr9 = {-36,10,-28,-42,17,83,87,79,51,-26,33,53,63,61,76,34,57,68,1,-30};
        System.out.println(solution.shortestSubarray(arr9, 484)); //9
        int[] arr10 = {17985,-36292,-23941,80618,20594,
                -6181,9181,65796,-25716,66593,-6873,34062,29878,852,-4767,-36415,11783,8085,-41063,-39940,74284,66272,82385,51634,-48550,9028,-30777,86509,44623,9413,-38369,-1822,46408,35217,72635,-16560,85373,52105,39477,3852,45974,-21593,15481,47280,73889,-42981,54978,95169,-19615,93133};
        System.out.println(solution.shortestSubarray(arr10, 387303)); //11
        int[] arr11 = {-22,73,-28,62,4,-21,-39,-21,-26,47,79,64,15,86,-20,-7,-24,-5,21,73};
        System.out.println(solution.shortestSubarray(arr11, 87)); //2
        int[] arr12 = {11,47,97,35,-46,59,46,51,59,80,14,-6,2,20,96,1,18,74,-17,71};
        System.out.println(solution.shortestSubarray(arr12, 282)); //5
        int[] arr13 = {39353,64606,-23508,5678,-17612,40217,15351,-12613,-37037,64183,68965,-19778,-41764,-21512,17700,-23100,77370,64076,53385,30915,18025,17577,10658,77805,56466,-2947,29423,50001,31803,9888,71251,-6466,77254,-30515,2903,76974,-49661,-10089,66626,-7065,-46652,84755,-37843,-5067,67963,92475,15340,15212,54320,-5286};
        System.out.println(solution.shortestSubarray(arr13, 207007)); //4
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int shortestSubarray(int[] A, int K) {
            int len = A.length;
            int sum = 0, begin = 0, res = -1;
            for (int i = 0; i < len; i++) {
                if (A[i] >= K) return 1;
                sum += A[i];
                if (sum < 1) {
                    sum = 0;
                    begin = i + 1;
                    continue;
                }
                for (int j = i - 1; A[j + 1] < 0; j--) {
                    A[j] = A[j + 1] + A[j];
                    A[j + 1] = 0;
                }
                if (sum >= K) {
                    while (sum - A[begin] >= K || A[begin] <= 0)
                        sum -= A[begin++];
                    int length = i - begin + 1;
                    if (res < 0 || res > length)
                        res = length;
                }
            }
            return res;
            /*int start = 0, sum = 0, count = -1;
            for(int i = 0; i < A.length; i++) {
                int num = A[i];
                if(num >= K) return 1;
                sum += num;
                if(sum >= K){
                    int temp = sum;
                    for(int j = start; j <= i; j++){
                        temp -= A[j];
                        if(temp >= K){
                            start = j+1;
                            sum = temp;
                        }
                    }
                    count = i - start + 1;
                    sum -= A[start];
                    start++;
                }
                if(sum <= 0){
                    sum = 0;
                    start = i+1;
                }else if(count != -1 && count - 1 == i-start+1){
                    sum -= A[start];
                    start++;
                    if(sum >= K){
                        int temp = sum;
                        for(int j = start; j <= i; j++){
                            temp -= A[j];
                            if(temp >= K){
                                start = j+1;
                                sum = temp;
                            }
                        }
                        count = i - start + 1;
                        System.out.println("start:" + start);
                        System.out.println("i:" + i);
                        sum -= A[start];
                        start++;
                        sum -= A[start];
                        start++;
                    }
                }*/
                /*if(sum >= K){
                    int temp = sum;
                    for(int j = start; j <= i; j++){
                        temp -= A[j];
                        if(temp >= K){
                            start = j+1;
                            sum = temp;
                        }
                    }
                    count = i - start + 1;
                    System.out.println(start);
                }else if(sum <= 0){
                    sum = 0;
                    start = i;
                }else{
                    sum -= A[start];
                    start++;
                }*/
                /*while(start != i && sum >= K){
                    if(A[start] > 0){
                        count = i - start + 1;
                        sum -= A[start];
                        start++;
                    }else{
                        while(start != i && A[start] <= 0){
                            count = i - start + 1;
                            sum -= A[start];
                            start++;
                        }
                    }
                }*/
                /*if(i == A.length - 1){
                    while (start != i) {
                        sum -= A[start];
                        start++;
                        if(sum >= K){
                            count = i - start + 1;
                        }
                    }
                }*/
                /*if(count == -1 && i >= 2 && num > A[start] && A[start] < 0){
                    sum -= A[start];
                    start++;
                }*/
            //}
            //return count;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}